package LeetCode热题HOT100;

public class p121买卖股票的最佳时机 {
    public int maxProfit(int[] prices) {
        //动态规划，只遍历一次
        int minPrice=Integer.MAX_VALUE;
        int maxProfit=0;

        for (int i = 0; i <prices.length; i++) {
            if (prices[i] < minPrice) {
                //当前股价 小于 minPrice，则更新minPrice
                minPrice=prices[i];
            }else if (prices[i]-minPrice > maxProfit) {
                //当前股价-最低股价 大于 最大利润maxProfit，则更新最大利润
                maxProfit=prices[i]-minPrice;
            }
        }

        return maxProfit;
    }

    public int maxProfit1(int[] prices) {
        //暴力求解，会超时
        int maxProfit=0;
        for (int i = 0; i <prices.length-1; i++) {
            for (int j = i+1; j <prices.length; j++) {
                int profit=prices[j]-prices[i];//计算当前利润
                if (profit > maxProfit) {
                    //如果 当前利润 > 最大利润，则更新最大利润
                    maxProfit=profit;
                }
            }
        }
        return maxProfit;
    }
}
